package primary.code08;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * 问题
 * <p>
 * 给定一个无重复值的、全为正数的数组，求一个子数组的最大指标m
 * 指标m = 子数组元素累加和 * 子数组内最小值
 * <p>
 * 分析
 * <p>
 * 遍历数组，假设当前元素为子数组的最小值，为了计算得到最大指标m，则期望子数组范围经可能大。
 * 最大的范围边界为当前元素左右两侧最近较小元素
 */
@Slf4j
public class Code08_subArrayMinProduct {

    public static int subArrayMinProduct(int[] arr) {
        // 参数合法验证...

        int res = Integer.MIN_VALUE;
        Stack<Integer> increaseStack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!increaseStack.isEmpty() && arr[i] <= arr[increaseStack.peek()]) {
                int top = increaseStack.pop();
                res = Math.max(res, arr[top] * sum(arr, increaseStack.isEmpty() ? 0 : increaseStack.peek() + 1, i - 1));
            }
            increaseStack.push(i);
        }
        while (!increaseStack.isEmpty()) {
            int top = increaseStack.pop();
            res = Math.max(res, arr[top] * sum(arr, increaseStack.isEmpty() ? 0 : increaseStack.peek() + 1, arr.length - 1));
        }
        return res;
    }

    public static int sum(int[] arr, int l, int r) {
        int res = 0;
        for (int i = l; i <= r; i++) {
            res += arr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        /*
            res:25, 最小值：5, 子数组左边界：0, 子数组右边界：0
            res:36, 最小值：6, 子数组左边界：2, 子数组右边界：2
            res:42, 最小值：3, 子数组左边界：0, 子数组右边界：2
            res:81, 最小值：9, 子数组左边界：4, 子数组右边界：4
            res:64, 最小值：8, 子数组左边界：6, 子数组右边界：6
            res:168, 最小值：7, 子数组左边界：4, 子数组右边界：6
            res:112, 最小值：4, 子数组左边界：4, 子数组右边界：7
            res:43, 最小值：1, 子数组左边界：0, 子数组右边界：7
            */
        int[] arr = {5, 3, 6, 1, 9, 7, 8, 4};
        int res = subArrayMinProduct(arr);
        log.info("array: {}, subArrayMinProduct: {}", arr, res);
    }
}
